package class03

import "math"

/*
	给定二维数组matrix，其中每个数都是正数，要求从左上到右下
	每一步只能向右或者向下，沿途经过的数字要累加起来
	最后请返回最小的路径和
	[0 0 0]
	[0 1 0]
	[0 0 0]
*/
func minPathSum1(m [][]int) int {
	return minPathSum1Process(m, 0, 0, 0)
}

func minPathSum1Process(m [][]int, x int, y int, sum int) int {
	if x >= len(m[0]) || y >= len(m) {
		return math.MaxInt
	}
	if x == len(m[0])-1 && y == len(m)-1 {
		return sum+m[x][y]
	}
	ans := math.MaxInt
	var p1, p2 int
	p1 = minPathSum1Process(m, x+1, y, sum+m[x][y])
	p2 = minPathSum1Process(m, x, y+1, sum+m[x][y])
	if p1 != math.MaxInt {
		ans = min(ans, p1)
	}
	if p2 != math.MaxInt {
		ans = min(ans, p2)
	}
	return ans
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func minPathSum2(m [][]int) int {
	return minPathSum2Process(m, 0, 0)
}

func minPathSum2Process(m [][]int, x int, y int) int {
	if x == len(m[0]) || y == len(m) {
		return math.MaxInt
	}
	if x == len(m[0])-1 && y == len(m)-1 {
		return m[x][y]
	}
	var ans, p1, p2 int
	ans = math.MaxInt
	p1 = minPathSum2Process(m, x+1, y)
	p2 = minPathSum2Process(m, x, y+1)
	if p1 != math.MaxInt {
		ans = min(ans, p1)
	}
	if p2 != math.MaxInt {
		ans = min(ans, p2)
	}
	if ans == math.MaxInt {
		return math.MaxInt
	}
	return ans+m[x][y]
}